package com.ahpu.lyf.linkedlist;

import java.util.ArrayList;

public class Josepfu {
    /*
    Josephu问题为:设编号为1，2，...n的n个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，数到m的那个人出列，
    它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
     */
    public static void main(String[] args) {
        CircleSingleLinkedList boyCircleSingleLinkedList = new CircleSingleLinkedList(5, 2);
        System.out.println("出队顺序为：" + boyCircleSingleLinkedList.getDequeueOrderList());
    }
}

//单向环形链表
class CircleSingleLinkedList {
    //一共有多少个孩子，题目中的k
    private final Integer boysNum;
    //报多少步数的人出列，题目中的m
    private final Integer step;
    private final Boy firstBoy;
    //出队顺序的数组
    ArrayList<Boy> dequeueOrderList;

    /**
     * 构造器
     *
     * @param boysNum 一共有多少个孩子
     * @param step    报多少步数的人出列
     */
    public CircleSingleLinkedList(Integer boysNum, Integer step) {
        this.boysNum = boysNum;
        this.step = step;
        //初始化第一个孩子编号为1
        this.firstBoy = new Boy(1);
        dequeueOrderList = new ArrayList<>();
        //第一个孩子自环
        firstBoy.setNext(firstBoy);
        //初始化单向环形链表
        dataCheck();
        initBoysCircleSingleLinkedList();
        printBoysCircleSingleLinkedList();
        getDequeueOrder(firstBoy);
    }

    public ArrayList<Boy> getDequeueOrderList() {
        return dequeueOrderList;
    }

    /**
     * 数据校验
     */
    private void dataCheck() {
        if (this.boysNum < 1) {
            System.out.println("孩子数量应大于1");
            System.exit(0);
        }
        if (this.step <= 1) {
            System.out.println("出队的报数差应大于1");
            System.exit(0);
        }

    }

    /**
     * 找到最后一个孩子节点的方法
     *
     * @return 返回最后一个孩子的节点
     */
    private Boy selectLastBoy() {
        //辅助节点，用于遍历
        Boy tempBoy = this.firstBoy;
        //当前节点的下一节点不是头结点则后移
        while (tempBoy.getNext() != this.firstBoy)
            tempBoy = tempBoy.getNext();
        //循环结束说明当前节点的下一节点是头结点，即当前节点是最后一个孩子的节点
        return tempBoy;
    }

    /**
     * 初始化单向环形链表的方法
     */
    private void initBoysCircleSingleLinkedList() {
        //第一个孩子节点已经初始化完成，从第二个孩子的编号开始添加
        for (int i = 2; i < this.boysNum + 1; i++) {
            //new一个孩子节点
            Boy boy = new Boy(i);
            //找到当前环形链表中最后一个节点（下一节点是头结点的节点即为最后一个节点）
            Boy lastBoy = selectLastBoy();
            //让最后一个节点指向这个要添加的孩子节点
            lastBoy.setNext(boy);
            //让要添加的孩子节点指向头结点
            boy.setNext(firstBoy);
        }
    }

    /**
     * 得到出队顺序
     * @param tempFitstBoy 下一个开始报数的孩子节点
     */
    private void getDequeueOrder(Boy tempFitstBoy) {
        // 1    2   3   4   5
        //辅助节点，找到要出队的节点的上一个节点
        Boy tempBoy = tempFitstBoy;
        for (int i = 0; i < this.step - 2; i++) {
            tempBoy = tempBoy.getNext();
        }
        //循环结束，此时的tempBoy指向要出队的节点的上一节点
        //获取要出队节点的下一个节点
        Boy nextBoy = tempBoy.getNext().getNext();
        //将要出对的节点添加到出队列表
        this.dequeueOrderList.add(tempBoy.getNext());
        //删除出队节点，即将要出队节点的上一节点指向要出队节点的下一节点
        tempBoy.setNext(nextBoy);
        //判断当前节点的下一节点是否为当前节点，是当前节点说明此时环形链表只有最后一个孩子节点
        if (tempBoy.getNext() == tempBoy) {
            //将最后一个节点添加到出队列表，退出递归
            this.dequeueOrderList.add(tempBoy);
            return;
        }
        //不是最后一个节点，递归将当前节点的下一节点（即从出队节点的下一节点开始继续找出队节点）
        getDequeueOrder(tempBoy.getNext());
    }

    /**
     * 从头节点开始打印这个单向环形链表
     */
    private void printBoysCircleSingleLinkedList() {
        System.out.println("打印单向环形链表为：");
        //辅助节点用于遍历
        Boy tempBoy = firstBoy;
        //下一节点不是头结点则后移
        while (tempBoy.getNext() != firstBoy) {
            System.out.println(tempBoy);
            tempBoy = tempBoy.getNext();
        }
        //循环结束时，辅助节点指向最后一个节点，但是由于跳出循环所以没有打印，打印一下最后一个节点
        System.out.println(tempBoy);
        //打印最后已经==一个节点的下一节点为头结点，说明这是个单向环形链表
        System.out.println("lastBoy.getNext() = " + tempBoy.getNext());
    }
}

//定义小孩节点
class Boy {
    private Integer no; //小孩的编号
    private Boy next;   //指向下一节点

    public Boy(Integer no) {
        this.no = no;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}
